package linkedlist;

//                                   模拟实现链表

//表示链表的每一个节点
class Node{
    //表示该节点的数据
    public String value;
    //表示下一个节点
    public Node next;
    public Node(String value){
        this.value = value;
        this.next = null;
    }
}

public class MyLinkedList {
    //表示链表的头节点
    public Node head = null;



    //头插
    public void addFirst(String value){
        //创建一个新节点
        Node newNode = new Node(value);
        //1.先把新节点指向链表头节点指向的位置
        newNode.next = head;
        //2.再把头节点指向新节点
        head = newNode;
    }
    //尾插
    public void addLast(String value){
        //判断 head 是否为 空的情况
        if (head == null){
            Node newNode = new Node(value);
            head = newNode;
            return;
        }
        //1.找到链表最后一个元素
        Node tail = head;
        for (tail = head; tail != null; tail = tail.next){
            //找到链表最后一个元素
            if (tail.next == null){
                break;
            }
        }
        //插入
        Node newNode = new Node(value);
        tail.next = newNode;
        newNode.next = null;
    }
    //指定下标插入
    public void add(int index, String value){
        //首先判断下标是否合法
        if (index < 0 || index > size()){
            throw new RuntimeException("下标超出异常");
        }
        //特殊情况处理
        if (index == 0){
            addFirst(value);
            return;
        }
        //插入操作
        Node newNode = new Node(value);
        //先找到插入位置的前一个位置的节点
        //前一个节点的下标为 index - 1
        Node prve = head;
        for (int i = 0; i < index - 1; i++){
            prve = prve.next;
        }
        //此时prve 就指向 index - 1 位置了
        newNode.next = prve.next;
        prve.next = newNode;
    }

    //表示链表的长度
    public int size(){
        Node cur = head;
        int size = 0;
        //遍历链表元素 ，每遍历一个元素 size++
        for (cur = head; cur != null; cur = cur.next){
            size++;
        }
        return size;
    }

    public String toString(){
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("[");
        //遍历链表的每个元素
        for (Node cur = head; cur != null; cur = cur.next){
            stringBuilder.append(cur.value);
            if (cur.next != null){
                stringBuilder.append(",");
            }
        }
        stringBuilder.append("]");
        return stringBuilder.toString();
    }
}
